package 力扣_滑动窗口.第二类模板;

import java.util.TreeMap;

/**
 * @author zx
 * @create 2022-05-10 21:43
 */
public class 绝对差不超过限制的最长连续子数组_1438 {
    /**
     * @return 这种窗口内求最大值、最小值的可以用滑动窗口 + 有序集合来解决
     * 注意点：根据题意注意窗口left边界的判断使用if还是使用while
     *
     * 时间复杂度：O(nlogn),其中 n 是数组长度.向有序集合中添加或删除元素都是 O(logn) 的时间复杂度.
     * 每个元素最多被添加与删除一次.
     * 空间复杂度：O(n),其中 n 是数组长度.最坏情况下有序集合将和原数组等大.
     */
    public int longestSubarray(int[] nums, int limit) {
        int left = 0;
        int res = 0;
        TreeMap<Integer,Integer> map = new TreeMap<>();
        for(int right = 0;right < nums.length;right++){
            if(map.containsKey(nums[right])){
                map.put(nums[right],map.get(nums[right]) + 1);
            }else{
                map.put(nums[right],1);
            }
            while(map.lastKey() - map.firstKey() > limit){
                map.put(nums[left],map.get(nums[left]) - 1);
                if(map.get(nums[left]) == 0){
                    map.remove(nums[left]);
                }
                left++;
            }
            res = Math.max(res,right - left + 1);
        }
        return res;
    }
}
